#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<stack>
using namespace std;

class Node{
public:
    Node(int value){
        this->value = value;
    }
public:
    int value;
};

class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        //建立并查集中的点集 
        for(int i = 0;i<pairs.size();++i){
            //一边建，一边合
            int left = pairs[i][0];
            int right = pairs[i][1];
            if(Nodes.find(left)==Nodes.end()){
                Nodes[left] = new Node(left);
                parents[Nodes[left]] = Nodes[left];
            }
            if(Nodes.find(right)==Nodes.end()){
                Nodes[right] = new Node(right);
                parents[Nodes[right]] = Nodes[right];
            }
            unionSet(left,right);
        }
        //把相同father的点提取出来
        string result = s;
        while(!Nodes.empty()){
            vector<int> regit;
            Node* father = findFather(Nodes.begin()->first);
            string son = "";
            for(map<int,Node*>::iterator i = Nodes.begin();i!=Nodes.end();++i){
                if(findFather(i->first)==father){
                    regit.push_back(i->first);
                    son += s[i->first];
                }
            }
            
            sort(son.begin(),son.end());
            for(int i = 0;i<regit.size();++i){
                result[regit[i]] = son[i];
                Nodes.erase(regit[i]);
            }
        }
        return result;
    }
    Node* findFather(int a){
        if(Nodes.find(a)==Nodes.end()){   
            return NULL;
        }
        Node* curr = Nodes[a];
        stack<Node*> path;
        while(parents[curr]!=curr){
            path.push(curr);
            curr = parents[curr];
        }
        while(!path.empty()){
            Node* temp = path.top();
            path.pop();
            parents[temp] = curr;
        }
        return curr;
    }
    bool isSameSet(int a,int b){
        if(Nodes.find(a)==Nodes.end()||Nodes.find(b)==Nodes.end()){
            return false;
        }
        else{
            return findFather(a)==findFather(b);
        }
    }

    void unionSet(int a,int b){
        if(Nodes.find(a)==Nodes.end()||Nodes.find(b)==Nodes.end()){
            return;
        }
        if(!isSameSet(a,b)){
            Node* afather = findFather(a);
            Node* bfather = findFather(b);
            parents[afather] = bfather;
        }
    }

public:
    map<int,Node*> Nodes;
    map<Node*,Node*> parents;
};


int main(){
    Solution S;
    string s = "pwqlmqm";
    vector<vector<int>> V = {{5,3},{3,0},{5,1},{1,1},{1,5},{3,0},{0,2}};
    string T = S.smallestStringWithSwaps(s,V);
    cout<<T<<endl;
}